<!DOCTYPE html>
<!-- saved from url=(0080)https://juejin.im/book/5bdc715fe51d454e755f75ef/section/5bdc723a6fb9a049c43d1843 -->
<html lang="zh-CN"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1"><meta name="viewport" content="width=device-width,initial-scale=1,user-scalable=no,viewport-fit=cover"><meta name="google-site-verification" content="cCHsgG9ktuCTgWgYfqCJql8AeR4gAne4DTZqztPoirE"><meta name="apple-itunes-app" content="app-id=987739104"><meta name="baidu-site-verification" content="qiK2a1kcFc"><meta name="360-site-verification" content="4c3c7d57d59f0e1a308462fbc7fd7e51"><meta name="sogou_site_verification" content="c49WUDZczQ"><style>body {
        font-size: 16px;
        line-height: 2;
      }
      a, button, input {
        margin: 1rem 1.5rem;
      }
      img {
        width: 0;
        height: 0;
      }
      #juejin {
        overflow-x: hidden;
      }</style><title data-vue-meta="true">前端面试之道 - yck - 掘金小册</title><link rel="apple-touch-icon" sizes="180x180" href="https://b-gold-cdn.xitu.io/favicons/v2/apple-touch-icon.png"><link rel="icon" type="image/png" sizes="32x32" href="https://b-gold-cdn.xitu.io/favicons/v2/favicon-32x32.png"><link rel="icon" type="image/png" sizes="16x16" href="https://b-gold-cdn.xitu.io/favicons/v2/favicon-16x16.png"><link rel="manifest" href="https://b-gold-cdn.xitu.io/favicons/v2/manifest.json"><link rel="mask-icon" href="https://b-gold-cdn.xitu.io/favicons/v2/safari-pinned-tab.svg" color="#5bbad5"><link rel="shortcut icon" href="https://b-gold-cdn.xitu.io/favicons/v2/favicon.ico"><meta name="msapplication-config" content="https://b-gold-cdn.xitu.io/favicons/v2/browserconfig.xml"><meta name="theme-color" content="#ffffff"><link rel="search" title="掘金" href="https://b-gold-cdn.xitu.io/conf/search.xml" type="application/opensearchdescription+xml"><link rel="stylesheet" href="./31-常见数据结构_files/ionicons.min.css"><link rel="stylesheet" href="./31-常见数据结构_files/iconfont.css"><link href="./31-常见数据结构_files/0.20e96f0e16539d696fbd.css" rel="stylesheet"><script async="" src="./31-常见数据结构_files/hm.js.下载"></script><script async="" src="./31-常见数据结构_files/analytics.js.下载"></script><script type="text/javascript" async="" src="./31-常见数据结构_files/vds.js.下载"></script><script charset="utf-8" src="./31-常见数据结构_files/13.46a6fc9d409a46c2798c.js.下载"></script><meta data-vmid="keywords" name="keywords" content="掘金,稀土,Vue.js,微信小程序,Kotlin,RxJava,React Native,Wireshark,敏捷开发,Bootstrap,OKHttp,正则表达式,WebGL,Webpack,Docker,MVVM" data-vue-meta="true"><meta data-vmid="description" name="description" content="掘金是一个帮助开发者成长的社区，是给开发者用的 Hacker News，给设计师用的 Designer News，和给产品经理用的 Medium。掘金的技术文章由稀土上聚集的技术大牛和极客共同编辑为你筛选出最优质的干货，其中包括：Android、iOS、前端、后端等方面的内容。用户每天都可以在这里找到技术世界的头条内容。与此同时，掘金内还有沸点、掘金翻译计划、线下活动、专栏文章等内容。即使你是 GitHub、StackOverflow、开源中国的用户，我们相信你也可以在这里有所收获。" data-vue-meta="true"></head><body><div id="juejin" data-v-514f306c=""><div class="global-component-box" data-v-514f306c=""><!----><div data-v-71cabb60="" data-v-514f306c="" class="alert-list alert-list"></div><!----><!----><!----><div class="emoji-barrage" data-v-e5f49d52="" data-v-514f306c=""><!----></div><div class="book-new-user-award-popup" style="display:none;" data-v-71b0e7b2="" data-v-514f306c=""><div class="content-box" style="display:;" data-v-71b0e7b2=""><div class="close ion-close-round" data-v-71b0e7b2=""></div><div class="header" data-v-71b0e7b2=""><div class="icon" data-v-71b0e7b2=""><img src="./31-常见数据结构_files/icon.a87e5ae.svg" data-v-71b0e7b2=""></div><div class="txt" data-v-71b0e7b2="">新人专享好礼</div></div><div class="desc" data-v-71b0e7b2="">凡未购买过小册的用户，均可领取三张 5 折新人专享券，购买小册时自动使用专享券，最高可节省 45 元。</div><div class="tickets" data-v-71b0e7b2=""><div class="ticket" data-v-71b0e7b2=""><div class="ticket__inner" data-v-71b0e7b2=""><div class="enjoy" data-v-71b0e7b2=""><span class="new-title" data-v-71b0e7b2="">小册新人 5 折券</span></div><div class="sale" data-v-71b0e7b2="">最高可省 15 元</div></div></div><div class="ticket" data-v-71b0e7b2=""><div class="ticket__inner" data-v-71b0e7b2=""><div class="enjoy" data-v-71b0e7b2=""><span class="new-title" data-v-71b0e7b2="">小册新人 5 折券</span></div><div class="sale" data-v-71b0e7b2="">最高可省 15 元</div></div></div><div class="ticket" data-v-71b0e7b2=""><div class="ticket__inner" data-v-71b0e7b2=""><div class="enjoy" data-v-71b0e7b2=""><span class="new-title" data-v-71b0e7b2="">小册新人 5 折券</span></div><div class="sale" data-v-71b0e7b2="">最高可省 15 元</div></div></div></div><div class="remark" data-v-71b0e7b2="">注：专享券的使用期限在领券的七天内。</div><div class="submit-btn" data-v-71b0e7b2="">一键领取</div></div><div class="model success" style="display:none;" data-v-71b0e7b2=""><div class="heading" data-v-71b0e7b2="">领取成功</div><div class="content-text" data-v-71b0e7b2="">购买小册时自动使用专享券</div><div class="btn-success-footer" data-v-71b0e7b2=""><div class="btn-ok" data-v-71b0e7b2="">知道了</div><div class="btn-ok btn-link" data-v-71b0e7b2="">前往小册首页</div></div></div><div class="model fail" style="display:none;" data-v-71b0e7b2=""><div class="heading" data-v-71b0e7b2="">领取失败</div><div class="content-text" data-v-71b0e7b2="">本活动仅适用于小册新用户</div><div class="btn-ok" data-v-71b0e7b2="">知道了</div></div></div><!----></div><!----><div data-v-097468bb="" data-v-514f306c="" class="book-read-view"><section data-v-097468bb="" class="book-section"><div data-v-097468bb="" class="book-summary"><div data-v-097468bb="" class="book-summary-masker"></div><div data-v-097468bb="" class="book-summary-inner"><div data-v-097468bb="" class="book-summary__header"><a data-v-097468bb="" href="https://juejin.im/books" target="" rel="" class="logo"><img data-v-097468bb="" src="./31-常见数据结构_files/logo.a7995ad.svg"></a><div data-v-097468bb="" class="label">小册</div><!----></div><!----><div data-v-d0eb2184="" data-v-097468bb="" class="book-directory book-directory bought"><a data-v-d0eb2184="" class="section section-link read"><div data-v-d0eb2184="" class="step"><div data-v-d0eb2184="" class="step-btn">1</div></div><div data-v-d0eb2184="" class="center"><div data-v-d0eb2184="" class="title">小册食用指南</div><!----><!----></div><!----></a><a data-v-d0eb2184="" class="section section-link read"><div data-v-d0eb2184="" class="step"><div data-v-d0eb2184="" class="step-btn">2</div></div><div data-v-d0eb2184="" class="center"><div data-v-d0eb2184="" class="title">JS 基础知识点及常考面试题（一）</div><!----><!----></div><!----></a><a data-v-d0eb2184="" class="section section-link read"><div data-v-d0eb2184="" class="step"><div data-v-d0eb2184="" class="step-btn">3</div></div><div data-v-d0eb2184="" class="center"><div data-v-d0eb2184="" class="title">JS 基础知识点及常考面试题（二）</div><!----><!----></div><!----></a><a data-v-d0eb2184="" class="section section-link read"><div data-v-d0eb2184="" class="step"><div data-v-d0eb2184="" class="step-btn">4</div></div><div data-v-d0eb2184="" class="center"><div data-v-d0eb2184="" class="title">ES6 知识点及常考面试题</div><!----><!----></div><!----></a><a data-v-d0eb2184="" class="section section-link read"><div data-v-d0eb2184="" class="step"><div data-v-d0eb2184="" class="step-btn">5</div></div><div data-v-d0eb2184="" class="center"><div data-v-d0eb2184="" class="title">JS 异步编程及常考面试题</div><!----><!----></div><!----></a><a data-v-d0eb2184="" class="section section-link read"><div data-v-d0eb2184="" class="step"><div data-v-d0eb2184="" class="step-btn">6</div></div><div data-v-d0eb2184="" class="center"><div data-v-d0eb2184="" class="title">手写 Promise</div><!----><!----></div><!----></a><a data-v-d0eb2184="" class="section section-link read"><div data-v-d0eb2184="" class="step"><div data-v-d0eb2184="" class="step-btn">7</div></div><div data-v-d0eb2184="" class="center"><div data-v-d0eb2184="" class="title">Event Loop</div><!----><!----></div><!----></a><a data-v-d0eb2184="" class="section section-link read"><div data-v-d0eb2184="" class="step"><div data-v-d0eb2184="" class="step-btn">8</div></div><div data-v-d0eb2184="" class="center"><div data-v-d0eb2184="" class="title">JS 进阶知识点及常考面试题</div><!----><!----></div><!----></a><a data-v-d0eb2184="" class="section section-link read"><div data-v-d0eb2184="" class="step"><div data-v-d0eb2184="" class="step-btn">9</div></div><div data-v-d0eb2184="" class="center"><div data-v-d0eb2184="" class="title">JS 思考题</div><!----><!----></div><!----></a><a data-v-d0eb2184="" class="section section-link read"><div data-v-d0eb2184="" class="step"><div data-v-d0eb2184="" class="step-btn">10</div></div><div data-v-d0eb2184="" class="center"><div data-v-d0eb2184="" class="title">DevTools Tips</div><!----><!----></div><!----></a><a data-v-d0eb2184="" class="section section-link read"><div data-v-d0eb2184="" class="step"><div data-v-d0eb2184="" class="step-btn">11</div></div><div data-v-d0eb2184="" class="center"><div data-v-d0eb2184="" class="title">浏览器基础知识点及常考面试题</div><!----><!----></div><!----></a><a data-v-d0eb2184="" class="section section-link read"><div data-v-d0eb2184="" class="step"><div data-v-d0eb2184="" class="step-btn">12</div></div><div data-v-d0eb2184="" class="center"><div data-v-d0eb2184="" class="title">浏览器缓存机制</div><!----><!----></div><!----></a><a data-v-d0eb2184="" class="section section-link read"><div data-v-d0eb2184="" class="step"><div data-v-d0eb2184="" class="step-btn">13</div></div><div data-v-d0eb2184="" class="center"><div data-v-d0eb2184="" class="title">浏览器渲染原理</div><!----><!----></div><!----></a><a data-v-d0eb2184="" class="section section-link read"><div data-v-d0eb2184="" class="step"><div data-v-d0eb2184="" class="step-btn">14</div></div><div data-v-d0eb2184="" class="center"><div data-v-d0eb2184="" class="title">安全防范知识点</div><!----><!----></div><!----></a><a data-v-d0eb2184="" class="section section-link read"><div data-v-d0eb2184="" class="step"><div data-v-d0eb2184="" class="step-btn">15</div></div><div data-v-d0eb2184="" class="center"><div data-v-d0eb2184="" class="title">从 V8 中看 JS 性能优化</div><!----><!----></div><!----></a><a data-v-d0eb2184="" class="section section-link read"><div data-v-d0eb2184="" class="step"><div data-v-d0eb2184="" class="step-btn">16</div></div><div data-v-d0eb2184="" class="center"><div data-v-d0eb2184="" class="title">性能优化琐碎事</div><!----><!----></div><!----></a><a data-v-d0eb2184="" class="section section-link read"><div data-v-d0eb2184="" class="step"><div data-v-d0eb2184="" class="step-btn">17</div></div><div data-v-d0eb2184="" class="center"><div data-v-d0eb2184="" class="title">Webpack 性能优化</div><!----><!----></div><!----></a><a data-v-d0eb2184="" class="section section-link read"><div data-v-d0eb2184="" class="step"><div data-v-d0eb2184="" class="step-btn">18</div></div><div data-v-d0eb2184="" class="center"><div data-v-d0eb2184="" class="title">实现小型打包工具</div><!----><!----></div><!----></a><a data-v-d0eb2184="" class="section section-link read"><div data-v-d0eb2184="" class="step"><div data-v-d0eb2184="" class="step-btn">19</div></div><div data-v-d0eb2184="" class="center"><div data-v-d0eb2184="" class="title">React 和 Vue 两大框架之间的相爱相杀</div><!----><!----></div><!----></a><a data-v-d0eb2184="" class="section section-link read"><div data-v-d0eb2184="" class="step"><div data-v-d0eb2184="" class="step-btn">20</div></div><div data-v-d0eb2184="" class="center"><div data-v-d0eb2184="" class="title">Vue 常考基础知识点</div><!----><!----></div><!----></a><a data-v-d0eb2184="" class="section section-link read"><div data-v-d0eb2184="" class="step"><div data-v-d0eb2184="" class="step-btn">21</div></div><div data-v-d0eb2184="" class="center"><div data-v-d0eb2184="" class="title">Vue 常考进阶知识点</div><!----><!----></div><!----></a><a data-v-d0eb2184="" class="section section-link read"><div data-v-d0eb2184="" class="step"><div data-v-d0eb2184="" class="step-btn">22</div></div><div data-v-d0eb2184="" class="center"><div data-v-d0eb2184="" class="title">React 常考基础知识点</div><!----><!----></div><!----></a><a data-v-d0eb2184="" class="section section-link read"><div data-v-d0eb2184="" class="step"><div data-v-d0eb2184="" class="step-btn">23</div></div><div data-v-d0eb2184="" class="center"><div data-v-d0eb2184="" class="title">React 常考进阶知识点</div><!----><!----></div><!----></a><a data-v-d0eb2184="" class="section section-link read"><div data-v-d0eb2184="" class="step"><div data-v-d0eb2184="" class="step-btn">24</div></div><div data-v-d0eb2184="" class="center"><div data-v-d0eb2184="" class="title">监控</div><!----><!----></div><!----></a><a data-v-d0eb2184="" class="section section-link read"><div data-v-d0eb2184="" class="step"><div data-v-d0eb2184="" class="step-btn">25</div></div><div data-v-d0eb2184="" class="center"><div data-v-d0eb2184="" class="title">UDP</div><!----><!----></div><!----></a><a data-v-d0eb2184="" class="section section-link read"><div data-v-d0eb2184="" class="step"><div data-v-d0eb2184="" class="step-btn">26</div></div><div data-v-d0eb2184="" class="center"><div data-v-d0eb2184="" class="title">TCP</div><!----><!----></div><!----></a><a data-v-d0eb2184="" class="section section-link read"><div data-v-d0eb2184="" class="step"><div data-v-d0eb2184="" class="step-btn">27</div></div><div data-v-d0eb2184="" class="center"><div data-v-d0eb2184="" class="title">HTTP 及 TLS</div><!----><!----></div><!----></a><a data-v-d0eb2184="" class="section section-link read"><div data-v-d0eb2184="" class="step"><div data-v-d0eb2184="" class="step-btn">28</div></div><div data-v-d0eb2184="" class="center"><div data-v-d0eb2184="" class="title">HTTP/2 及 HTTP/3</div><!----><!----></div><!----></a><a data-v-d0eb2184="" class="section section-link read"><div data-v-d0eb2184="" class="step"><div data-v-d0eb2184="" class="step-btn">29</div></div><div data-v-d0eb2184="" class="center"><div data-v-d0eb2184="" class="title">输入 URL 到页面渲染的整个流程</div><!----><!----></div><!----></a><a data-v-d0eb2184="" class="section section-link read"><div data-v-d0eb2184="" class="step"><div data-v-d0eb2184="" class="step-btn">30</div></div><div data-v-d0eb2184="" class="center"><div data-v-d0eb2184="" class="title">设计模式</div><!----><!----></div><!----></a><a data-v-d0eb2184="" class="section route-active section-link"><div data-v-d0eb2184="" class="step"><div data-v-d0eb2184="" class="step-btn">31</div></div><div data-v-d0eb2184="" class="center"><div data-v-d0eb2184="" class="title">常见数据结构</div><!----><!----></div><!----></a><a data-v-d0eb2184="" class="section section-link"><div data-v-d0eb2184="" class="step"><div data-v-d0eb2184="" class="step-btn">32</div></div><div data-v-d0eb2184="" class="center"><div data-v-d0eb2184="" class="title">常考算法题解析</div><!----><!----></div><!----></a><a data-v-d0eb2184="" class="section section-link"><div data-v-d0eb2184="" class="step"><div data-v-d0eb2184="" class="step-btn">33</div></div><div data-v-d0eb2184="" class="center"><div data-v-d0eb2184="" class="title">CSS 常考面试题资料</div><!----><!----></div><!----></a><a data-v-d0eb2184="" class="section section-link"><div data-v-d0eb2184="" class="step"><div data-v-d0eb2184="" class="step-btn">34</div></div><div data-v-d0eb2184="" class="center"><div data-v-d0eb2184="" class="title">如何写好一封简历</div><!----><!----></div><!----></a><a data-v-d0eb2184="" class="section section-link"><div data-v-d0eb2184="" class="step"><div data-v-d0eb2184="" class="step-btn">35</div></div><div data-v-d0eb2184="" class="center"><div data-v-d0eb2184="" class="title">面试常用技巧</div><!----><!----></div><!----></a><a data-v-d0eb2184="" class="section section-link"><div data-v-d0eb2184="" class="step"><div data-v-d0eb2184="" class="step-btn">36</div></div><div data-v-d0eb2184="" class="center"><div data-v-d0eb2184="" class="title">前方的路，让我们结伴同行</div><!----><!----></div><!----></a></div><div data-v-097468bb="" class="book-summary__footer"><div data-v-097468bb="" class="qr-icon"><img data-v-097468bb="" src="./31-常见数据结构_files/qr-icon.881015a.svg"></div><div data-v-097468bb="" class="qr-tips"><span data-v-097468bb="" class="ion-close"></span><div data-v-097468bb="" class="title"><span data-v-097468bb="">关注公众号</span><span data-v-097468bb="">领取优惠码</span></div><div data-v-097468bb="" class="qr-img"><img data-v-097468bb="" src="./31-常见数据结构_files/wx-qr.13d8b4d.png"></div></div></div></div></div><div data-v-097468bb="" class="book-content"><div data-v-097468bb="" class="book-content-inner"><div data-v-097468bb="" class="book-content__header visible"><div data-v-097468bb="" class="switch"><img data-v-097468bb="" src="./31-常见数据结构_files/icon.3e69d5a.svg"></div><div data-v-097468bb="" class="menu"><img data-v-097468bb="" src="./31-常见数据结构_files/menu.74b9add.svg"></div><div data-v-097468bb="" class="title"><a data-v-097468bb="" href="https://juejin.im/book/5bdc715fe51d454e755f75ef" target="" rel="">前端面试之道</a></div><div data-v-629272fe="" data-v-097468bb="" class="user-auth user-auth"><div data-v-629272fe="" class="nav-item menu"><div data-v-3b1ba6d2="" data-v-afcc6e34="" data-v-629272fe="" data-src="https://b-gold-cdn.xitu.io/v3/static/img/default-avatar.e30559a.svg" class="lazy avatar avatar loaded" style="background-image: url(&quot;https://b-gold-cdn.xitu.io/v3/static/img/default-avatar.e30559a.svg&quot;);"></div><div data-v-629272fe="" class="nav-menu user-dropdown-list" style="display: none;"><ul data-v-629272fe="" class="nav-menu-item-group"><li data-v-629272fe="" class="nav-menu-item"><a data-v-629272fe=""><i data-v-629272fe="" class="fengwei fw-write"></i><span data-v-629272fe="">写文章</span></a></li><!----><li data-v-629272fe="" class="nav-menu-item"><a data-v-629272fe=""><i data-v-629272fe="" class="fengwei fw-draft"></i><span data-v-629272fe="">草稿</span></a></li></ul><ul data-v-629272fe="" class="nav-menu-item-group"><li data-v-629272fe="" class="nav-menu-item"><a data-v-629272fe="" href="https://juejin.im/user/5c2c54ca6fb9a049cb18da5a"><i data-v-629272fe="" class="fengwei fw-person"></i><span data-v-629272fe="">我的主页</span></a></li><li data-v-629272fe="" class="nav-menu-item"><a data-v-629272fe="" href="https://juejin.im/user/5c2c54ca6fb9a049cb18da5a/likes"><i data-v-629272fe="" class="fengwei fw-like"></i><span data-v-629272fe="">我喜欢的</span></a></li><!----><li data-v-629272fe="" class="nav-menu-item"><a data-v-629272fe="" href="https://juejin.im/user/5c2c54ca6fb9a049cb18da5a/collections"><i data-v-629272fe="" class="fengwei fw-collection"></i><span data-v-629272fe="">我的收藏集</span></a></li><li data-v-629272fe="" class="nav-menu-item"><a data-v-629272fe="" href="https://juejin.im/user/5c2c54ca6fb9a049cb18da5a/books?type=bought"><i data-v-629272fe="" class="fengwei fw-bought"></i><span data-v-629272fe="">已购</span></a></li><!----><li data-v-629272fe="" class="nav-menu-item"><a data-v-629272fe="" href="https://juejin.im/subscribe"><i data-v-629272fe="" class="fengwei fw-tag"></i><span data-v-629272fe="">标签管理</span></a></li></ul><ul data-v-629272fe="" class="nav-menu-item-group"><li data-v-629272fe="" class="nav-menu-item"><a data-v-629272fe="" href="https://juejin.im/user/settings"><i data-v-629272fe="" class="fengwei fw-setting"></i><span data-v-629272fe="">设置</span></a></li><li data-v-629272fe="" class="nav-menu-item more"><a data-v-629272fe=""><i data-v-629272fe="" class="fengwei fw-info"></i><span data-v-629272fe="">关于</span><i data-v-629272fe="" class="ion-chevron-right more-icon"></i></a><div data-v-629272fe="" class="nav-menu more-dropdown-list"><ul data-v-629272fe="" class="nav-menu-item-group"><li data-v-629272fe="" class="nav-menu-item"><a data-v-629272fe="" href="https://juejin.im/app" target="_blank">下载应用</a></li><li data-v-629272fe="" class="nav-menu-item"><a data-v-629272fe="" href="https://juejin.im/about" target="_blank">关于</a></li><li data-v-629272fe="" class="nav-menu-item"><a data-v-629272fe="" href="https://xitu.io/jobs" target="_blank">加入我们</a></li><li data-v-629272fe="" class="nav-menu-item"><a data-v-629272fe="" href="https://github.com/xitu/gold-miner" rel="nofollow noopener noreferrer" target="_blank">翻译计划</a></li><li data-v-629272fe="" class="nav-menu-item"><a data-v-629272fe="" href="https://bd.juejin.im/?utm_campaign=bd&amp;utm_source=web&amp;utm_medium=nav" target="_blank">合作伙伴</a></li></ul></div></li></ul><ul data-v-629272fe="" class="nav-menu-item-group"><li data-v-629272fe="" class="nav-menu-item"><a data-v-629272fe=""><i data-v-629272fe="" class="fengwei fw-logout"></i><span data-v-629272fe="">登出</span></a></li></ul></div></div><!----></div><!----></div><div data-v-097468bb="" class="book-body transition--prev"><div data-v-5602b343="" data-v-097468bb="" class="section-view book-section-content"><div data-v-05bbf43a="" data-v-5602b343="" class="section-content"><div data-v-05bbf43a="" class="section-page book-section-view"><div data-v-05bbf43a="" class="entry-content article-content"><h1 class="heading" data-id="heading-0">常见数据结构</h1>
<p>这一章节我们将来学习数据结构的内容。经常会有人提问说：学习数据结构或者算法对于前端工程师有用么？</p>
<p>总的来说，这些基础学科在短期内收效确实甚微，但是我们首先不要将自己局限在前端工程师这点上。笔者之前是做 iOS 开发的，转做前端以后，只有两个技能还对我有用：</p>
<ol>
<li>基础学科内容，比如：网络知识、数据结构算法</li>
<li>编程思想</li>
</ol>
<p>其他 iOS 上积累的经验，转行以后基本就没多大用处了。所以说，当我们把视野放到编程这个角度去说，数据结构算法一定是有用的，并且也是你未来的一个天花板。可以不花费集中的时间去学习这些内容，但是一定需要时常去学习一点，因为这些技能可以实实在在提升你写代码的能力。</p>
<blockquote class="warning"><p>这一章节的内容信息量会很大，不适合在非电脑环境下阅读，请各位打开代码编辑器，一行行的敲代码，单纯阅读是学习不了数据结构的。
</p></blockquote><h2 class="heading" data-id="heading-1">时间复杂度</h2>
<p>在进入正题之前，我们先来了解下什么是时间复杂度。</p>
<p>通常使用最差的时间复杂度来衡量一个算法的好坏。</p>
<p>常数时间 O(1) 代表这个操作和数据量没关系，是一个固定时间的操作，比如说四则运算。</p>
<p>对于一个算法来说，可能会计算出操作次数为 aN + 1，N 代表数据量。那么该算法的时间复杂度就是 O(N)。因为我们在计算时间复杂度的时候，数据量通常是非常大的，这时候低阶项和常数项可以忽略不计。</p>
<p>当然可能会出现两个算法都是 O(N) 的时间复杂度，那么对比两个算法的好坏就要通过对比低阶项和常数项了。</p>
<h2 class="heading" data-id="heading-2">栈</h2>
<h3 class="heading" data-id="heading-3">概念</h3>
<p>栈是一个线性结构，在计算机中是一个相当常见的数据结构。</p>
<p>栈的特点是只能在某一端添加或删除数据，遵循先进后出的原则</p>
<p></p><figure><img class="lazyload inited loaded" data-src="https://user-gold-cdn.xitu.io/2018/5/20/1637b785d2d68735?imageView2/0/w/1280/h/960/format/webp/ignore-error/1" data-width="640" data-height="460" src="./31-常见数据结构_files/1637b785d2d68735"><figcaption></figcaption></figure><p></p>
<h3 class="heading" data-id="heading-4">实现</h3>
<p>每种数据结构都可以用很多种方式来实现，其实可以把栈看成是数组的一个子集，所以这里使用数组来实现</p>
<pre><code class="hljs js" lang="js"><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Stack</span> </span>{
  <span class="hljs-keyword">constructor</span>() {
    <span class="hljs-keyword">this</span>.stack = []
  }
  push(item) {
    <span class="hljs-keyword">this</span>.stack.push(item)
  }
  pop() {
    <span class="hljs-keyword">this</span>.stack.pop()
  }
  peek() {
    <span class="hljs-keyword">return</span> <span class="hljs-keyword">this</span>.stack[<span class="hljs-keyword">this</span>.getCount() - <span class="hljs-number">1</span>]
  }
  getCount() {
    <span class="hljs-keyword">return</span> <span class="hljs-keyword">this</span>.stack.length
  }
  isEmpty() {
    <span class="hljs-keyword">return</span> <span class="hljs-keyword">this</span>.getCount() === <span class="hljs-number">0</span>
  }
}
</code></pre><h2 class="heading" data-id="heading-5">应用</h2>
<p>选取了 <a target="_blank" href="https://link.juejin.im/?target=https%3A%2F%2Fleetcode.com%2Fproblems%2Fvalid-parentheses%2Fsubmissions%2F1" rel="nofollow noopener noreferrer">LeetCode 上序号为 20 的题目</a></p>
<p>题意是匹配括号，可以通过栈的特性来完成这道题目</p>
<pre><code class="hljs js" lang="js"><span class="hljs-keyword">var</span> isValid = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">s</span>) </span>{
  <span class="hljs-keyword">let</span> map = {
    <span class="hljs-string">'('</span>: <span class="hljs-number">-1</span>,
    <span class="hljs-string">')'</span>: <span class="hljs-number">1</span>,
    <span class="hljs-string">'['</span>: <span class="hljs-number">-2</span>,
    <span class="hljs-string">']'</span>: <span class="hljs-number">2</span>,
    <span class="hljs-string">'{'</span>: <span class="hljs-number">-3</span>,
    <span class="hljs-string">'}'</span>: <span class="hljs-number">3</span>
  }
  <span class="hljs-keyword">let</span> stack = []
  <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-number">0</span>; i &lt; s.length; i++) {
    <span class="hljs-keyword">if</span> (map[s[i]] &lt; <span class="hljs-number">0</span>) {
      stack.push(s[i])
    } <span class="hljs-keyword">else</span> {
      <span class="hljs-keyword">let</span> last = stack.pop()
      <span class="hljs-keyword">if</span> (map[last] + map[s[i]] != <span class="hljs-number">0</span>) <span class="hljs-keyword">return</span> <span class="hljs-literal">false</span>
    }
  }
  <span class="hljs-keyword">if</span> (stack.length &gt; <span class="hljs-number">0</span>) <span class="hljs-keyword">return</span> <span class="hljs-literal">false</span>
  <span class="hljs-keyword">return</span> <span class="hljs-literal">true</span>
};
</code></pre><p>其实在 Vue 中关于模板解析的代码，就有应用到匹配尖括号的内容。</p>
<h2 class="heading" data-id="heading-6">队列</h2>
<h3 class="heading" data-id="heading-7">概念</h3>
<p>队列是一个线性结构，特点是在某一端添加数据，在另一端删除数据，遵循先进先出的原则。</p>
<p></p><figure><img class="lazyload inited loaded" data-src="https://user-gold-cdn.xitu.io/2018/5/20/1637cba2a6155793?imageView2/0/w/1280/h/960/format/webp/ignore-error/1" data-width="640" data-height="419" src="./31-常见数据结构_files/1637cba2a6155793"><figcaption></figcaption></figure><p></p>
<h3 class="heading" data-id="heading-8">实现</h3>
<p>这里会讲解两种实现队列的方式，分别是单链队列和循环队列。</p>
<h4 class="heading" data-id="heading-9">单链队列</h4>
<pre><code class="hljs js" lang="js"><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Queue</span> </span>{
  <span class="hljs-keyword">constructor</span>() {
    <span class="hljs-keyword">this</span>.queue = []
  }
  enQueue(item) {
    <span class="hljs-keyword">this</span>.queue.push(item)
  }
  deQueue() {
    <span class="hljs-keyword">return</span> <span class="hljs-keyword">this</span>.queue.shift()
  }
  getHeader() {
    <span class="hljs-keyword">return</span> <span class="hljs-keyword">this</span>.queue[<span class="hljs-number">0</span>]
  }
  getLength() {
    <span class="hljs-keyword">return</span> <span class="hljs-keyword">this</span>.queue.length
  }
  isEmpty() {
    <span class="hljs-keyword">return</span> <span class="hljs-keyword">this</span>.getLength() === <span class="hljs-number">0</span>
  }
}
</code></pre><p>因为单链队列在出队操作的时候需要 O(n) 的时间复杂度，所以引入了循环队列。循环队列的出队操作平均是 O(1) 的时间复杂度。</p>
<h4 class="heading" data-id="heading-10">循环队列</h4>
<pre><code class="hljs js" lang="js"><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">SqQueue</span> </span>{
  <span class="hljs-keyword">constructor</span>(length) {
    <span class="hljs-keyword">this</span>.queue = <span class="hljs-keyword">new</span> <span class="hljs-built_in">Array</span>(length + <span class="hljs-number">1</span>)
    <span class="hljs-comment">// 队头</span>
    <span class="hljs-keyword">this</span>.first = <span class="hljs-number">0</span>
    <span class="hljs-comment">// 队尾</span>
    <span class="hljs-keyword">this</span>.last = <span class="hljs-number">0</span>
    <span class="hljs-comment">// 当前队列大小</span>
    <span class="hljs-keyword">this</span>.size = <span class="hljs-number">0</span>
  }
  enQueue(item) {
    <span class="hljs-comment">// 判断队尾 + 1 是否为队头</span>
    <span class="hljs-comment">// 如果是就代表需要扩容数组</span>
    <span class="hljs-comment">// % this.queue.length 是为了防止数组越界</span>
    <span class="hljs-keyword">if</span> (<span class="hljs-keyword">this</span>.first === (<span class="hljs-keyword">this</span>.last + <span class="hljs-number">1</span>) % <span class="hljs-keyword">this</span>.queue.length) {
      <span class="hljs-keyword">this</span>.resize(<span class="hljs-keyword">this</span>.getLength() * <span class="hljs-number">2</span> + <span class="hljs-number">1</span>)
    }
    <span class="hljs-keyword">this</span>.queue[<span class="hljs-keyword">this</span>.last] = item
    <span class="hljs-keyword">this</span>.size++
    <span class="hljs-keyword">this</span>.last = (<span class="hljs-keyword">this</span>.last + <span class="hljs-number">1</span>) % <span class="hljs-keyword">this</span>.queue.length
  }
  deQueue() {
    <span class="hljs-keyword">if</span> (<span class="hljs-keyword">this</span>.isEmpty()) {
      <span class="hljs-keyword">throw</span> <span class="hljs-built_in">Error</span>(<span class="hljs-string">'Queue is empty'</span>)
    }
    <span class="hljs-keyword">let</span> r = <span class="hljs-keyword">this</span>.queue[<span class="hljs-keyword">this</span>.first]
    <span class="hljs-keyword">this</span>.queue[<span class="hljs-keyword">this</span>.first] = <span class="hljs-literal">null</span>
    <span class="hljs-keyword">this</span>.first = (<span class="hljs-keyword">this</span>.first + <span class="hljs-number">1</span>) % <span class="hljs-keyword">this</span>.queue.length
    <span class="hljs-keyword">this</span>.size--
    <span class="hljs-comment">// 判断当前队列大小是否过小</span>
    <span class="hljs-comment">// 为了保证不浪费空间，在队列空间等于总长度四分之一时</span>
    <span class="hljs-comment">// 且不为 2 时缩小总长度为当前的一半</span>
    <span class="hljs-keyword">if</span> (<span class="hljs-keyword">this</span>.size === <span class="hljs-keyword">this</span>.getLength() / <span class="hljs-number">4</span> &amp;&amp; <span class="hljs-keyword">this</span>.getLength() / <span class="hljs-number">2</span> !== <span class="hljs-number">0</span>) {
      <span class="hljs-keyword">this</span>.resize(<span class="hljs-keyword">this</span>.getLength() / <span class="hljs-number">2</span>)
    }
    <span class="hljs-keyword">return</span> r
  }
  getHeader() {
    <span class="hljs-keyword">if</span> (<span class="hljs-keyword">this</span>.isEmpty()) {
      <span class="hljs-keyword">throw</span> <span class="hljs-built_in">Error</span>(<span class="hljs-string">'Queue is empty'</span>)
    }
    <span class="hljs-keyword">return</span> <span class="hljs-keyword">this</span>.queue[<span class="hljs-keyword">this</span>.first]
  }
  getLength() {
    <span class="hljs-keyword">return</span> <span class="hljs-keyword">this</span>.queue.length - <span class="hljs-number">1</span>
  }
  isEmpty() {
    <span class="hljs-keyword">return</span> <span class="hljs-keyword">this</span>.first === <span class="hljs-keyword">this</span>.last
  }
  resize(length) {
    <span class="hljs-keyword">let</span> q = <span class="hljs-keyword">new</span> <span class="hljs-built_in">Array</span>(length)
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-number">0</span>; i &lt; length; i++) {
      q[i] = <span class="hljs-keyword">this</span>.queue[(i + <span class="hljs-keyword">this</span>.first) % <span class="hljs-keyword">this</span>.queue.length]
    }
    <span class="hljs-keyword">this</span>.queue = q
    <span class="hljs-keyword">this</span>.first = <span class="hljs-number">0</span>
    <span class="hljs-keyword">this</span>.last = <span class="hljs-keyword">this</span>.size
  }
}
</code></pre><h2 class="heading" data-id="heading-11">链表</h2>
<h3 class="heading" data-id="heading-12">概念</h3>
<p>链表是一个线性结构，同时也是一个天然的递归结构。链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。</p>
<p></p><figure><img class="lazyload inited loaded" data-src="https://user-gold-cdn.xitu.io/2018/5/22/16388487759b1152?imageView2/0/w/1280/h/960/format/webp/ignore-error/1" data-width="1060" data-height="178" src="./31-常见数据结构_files/16388487759b1152"><figcaption></figcaption></figure><p></p>
<h3 class="heading" data-id="heading-13">实现</h3>
<p><strong>单向链表</strong></p>
<pre><code class="hljs js" lang="js"><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Node</span> </span>{
  <span class="hljs-keyword">constructor</span>(v, next) {
    <span class="hljs-keyword">this</span>.value = v
    <span class="hljs-keyword">this</span>.next = next
  }
}
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">LinkList</span> </span>{
  <span class="hljs-keyword">constructor</span>() {
    <span class="hljs-comment">// 链表长度</span>
    <span class="hljs-keyword">this</span>.size = <span class="hljs-number">0</span>
    <span class="hljs-comment">// 虚拟头部</span>
    <span class="hljs-keyword">this</span>.dummyNode = <span class="hljs-keyword">new</span> Node(<span class="hljs-literal">null</span>, <span class="hljs-literal">null</span>)
  }
  find(header, index, currentIndex) {
    <span class="hljs-keyword">if</span> (index === currentIndex) <span class="hljs-keyword">return</span> header
    <span class="hljs-keyword">return</span> <span class="hljs-keyword">this</span>.find(header.next, index, currentIndex + <span class="hljs-number">1</span>)
  }
  addNode(v, index) {
    <span class="hljs-keyword">this</span>.checkIndex(index)
    <span class="hljs-comment">// 当往链表末尾插入时，prev.next 为空</span>
    <span class="hljs-comment">// 其他情况时，因为要插入节点，所以插入的节点</span>
    <span class="hljs-comment">// 的 next 应该是 prev.next</span>
    <span class="hljs-comment">// 然后设置 prev.next 为插入的节点</span>
    <span class="hljs-keyword">let</span> prev = <span class="hljs-keyword">this</span>.find(<span class="hljs-keyword">this</span>.dummyNode, index, <span class="hljs-number">0</span>)
    prev.next = <span class="hljs-keyword">new</span> Node(v, prev.next)
    <span class="hljs-keyword">this</span>.size++
    <span class="hljs-keyword">return</span> prev.next
  }
  insertNode(v, index) {
    <span class="hljs-keyword">return</span> <span class="hljs-keyword">this</span>.addNode(v, index)
  }
  addToFirst(v) {
    <span class="hljs-keyword">return</span> <span class="hljs-keyword">this</span>.addNode(v, <span class="hljs-number">0</span>)
  }
  addToLast(v) {
    <span class="hljs-keyword">return</span> <span class="hljs-keyword">this</span>.addNode(v, <span class="hljs-keyword">this</span>.size)
  }
  removeNode(index, isLast) {
    <span class="hljs-keyword">this</span>.checkIndex(index)
    index = isLast ? index - <span class="hljs-number">1</span> : index
    <span class="hljs-keyword">let</span> prev = <span class="hljs-keyword">this</span>.find(<span class="hljs-keyword">this</span>.dummyNode, index, <span class="hljs-number">0</span>)
    <span class="hljs-keyword">let</span> node = prev.next
    prev.next = node.next
    node.next = <span class="hljs-literal">null</span>
    <span class="hljs-keyword">this</span>.size--
    <span class="hljs-keyword">return</span> node
  }
  removeFirstNode() {
    <span class="hljs-keyword">return</span> <span class="hljs-keyword">this</span>.removeNode(<span class="hljs-number">0</span>)
  }
  removeLastNode() {
    <span class="hljs-keyword">return</span> <span class="hljs-keyword">this</span>.removeNode(<span class="hljs-keyword">this</span>.size, <span class="hljs-literal">true</span>)
  }
  checkIndex(index) {
    <span class="hljs-keyword">if</span> (index &lt; <span class="hljs-number">0</span> || index &gt; <span class="hljs-keyword">this</span>.size) <span class="hljs-keyword">throw</span> <span class="hljs-built_in">Error</span>(<span class="hljs-string">'Index error'</span>)
  }
  getNode(index) {
    <span class="hljs-keyword">this</span>.checkIndex(index)
    <span class="hljs-keyword">if</span> (<span class="hljs-keyword">this</span>.isEmpty()) <span class="hljs-keyword">return</span>
    <span class="hljs-keyword">return</span> <span class="hljs-keyword">this</span>.find(<span class="hljs-keyword">this</span>.dummyNode, index, <span class="hljs-number">0</span>).next
  }
  isEmpty() {
    <span class="hljs-keyword">return</span> <span class="hljs-keyword">this</span>.size === <span class="hljs-number">0</span>
  }
  getSize() {
    <span class="hljs-keyword">return</span> <span class="hljs-keyword">this</span>.size
  }
}
</code></pre><h2 class="heading" data-id="heading-14">树</h2>
<h3 class="heading" data-id="heading-15">二叉树</h3>
<p>树拥有很多种结构，二叉树是树中最常用的结构，同时也是一个天然的递归结构。</p>
<p>二叉树拥有一个根节点，每个节点至多拥有两个子节点，分别为：左节点和右节点。树的最底部节点称之为叶节点，当一颗树的叶数量数量为满时，该树可以称之为满二叉树。</p>
<p></p><figure><img class="lazyload inited loaded" data-src="https://user-gold-cdn.xitu.io/2018/5/22/163884f74c9f4e4d?imageView2/0/w/1280/h/960/format/webp/ignore-error/1" data-width="320" data-height="267" src="./31-常见数据结构_files/163884f74c9f4e4d"><figcaption></figcaption></figure><p></p>
<h3 class="heading" data-id="heading-16">二分搜索树</h3>
<p>二分搜索树也是二叉树，拥有二叉树的特性。但是区别在于二分搜索树每个节点的值都比他的左子树的值大，比右子树的值小。</p>
<p>这种存储方式很适合于数据搜索。如下图所示，当需要查找 6 的时候，因为需要查找的值比根节点的值大，所以只需要在根节点的右子树上寻找，大大提高了搜索效率。</p>
<p></p><figure><img class="lazyload inited loaded" data-src="https://user-gold-cdn.xitu.io/2018/5/22/1638850ba7458208?imageView2/0/w/1280/h/960/format/webp/ignore-error/1" data-width="596" data-height="485" src="./31-常见数据结构_files/1638850ba7458208"><figcaption></figcaption></figure><p></p>
<h3 class="heading" data-id="heading-17">实现</h3>
<pre><code class="hljs js" lang="js"><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Node</span> </span>{
  <span class="hljs-keyword">constructor</span>(value) {
    <span class="hljs-keyword">this</span>.value = value
    <span class="hljs-keyword">this</span>.left = <span class="hljs-literal">null</span>
    <span class="hljs-keyword">this</span>.right = <span class="hljs-literal">null</span>
  }
}
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">BST</span> </span>{
  <span class="hljs-keyword">constructor</span>() {
    <span class="hljs-keyword">this</span>.root = <span class="hljs-literal">null</span>
    <span class="hljs-keyword">this</span>.size = <span class="hljs-number">0</span>
  }
  getSize() {
    <span class="hljs-keyword">return</span> <span class="hljs-keyword">this</span>.size
  }
  isEmpty() {
    <span class="hljs-keyword">return</span> <span class="hljs-keyword">this</span>.size === <span class="hljs-number">0</span>
  }
  addNode(v) {
    <span class="hljs-keyword">this</span>.root = <span class="hljs-keyword">this</span>._addChild(<span class="hljs-keyword">this</span>.root, v)
  }
  <span class="hljs-comment">// 添加节点时，需要比较添加的节点值和当前</span>
  <span class="hljs-comment">// 节点值的大小</span>
  _addChild(node, v) {
    <span class="hljs-keyword">if</span> (!node) {
      <span class="hljs-keyword">this</span>.size++
      <span class="hljs-keyword">return</span> <span class="hljs-keyword">new</span> Node(v)
    }
    <span class="hljs-keyword">if</span> (node.value &gt; v) {
      node.left = <span class="hljs-keyword">this</span>._addChild(node.left, v)
    } <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (node.value &lt; v) {
      node.right = <span class="hljs-keyword">this</span>._addChild(node.right, v)
    }
    <span class="hljs-keyword">return</span> node
  }
}
</code></pre><p>以上是最基本的二分搜索树实现，接下来实现树的遍历。</p>
<p>对于树的遍历来说，有三种遍历方法，分别是先序遍历、中序遍历、后序遍历。三种遍历的区别在于何时访问节点。在遍历树的过程中，每个节点都会遍历三次，分别是遍历到自己，遍历左子树和遍历右子树。如果需要实现先序遍历，那么只需要第一次遍历到节点时进行操作即可。</p>
<pre><code class="hljs js" lang="js"><span class="hljs-comment">// 先序遍历可用于打印树的结构</span>
<span class="hljs-comment">// 先序遍历先访问根节点，然后访问左节点，最后访问右节点。</span>
preTraversal() {
  <span class="hljs-keyword">this</span>._pre(<span class="hljs-keyword">this</span>.root)
}
_pre(node) {
  <span class="hljs-keyword">if</span> (node) {
    <span class="hljs-built_in">console</span>.log(node.value)
    <span class="hljs-keyword">this</span>._pre(node.left)
    <span class="hljs-keyword">this</span>._pre(node.right)
  }
}
<span class="hljs-comment">// 中序遍历可用于排序</span>
<span class="hljs-comment">// 对于 BST 来说，中序遍历可以实现一次遍历就</span>
<span class="hljs-comment">// 得到有序的值</span>
<span class="hljs-comment">// 中序遍历表示先访问左节点，然后访问根节点，最后访问右节点。</span>
midTraversal() {
  <span class="hljs-keyword">this</span>._mid(<span class="hljs-keyword">this</span>.root)
}
_mid(node) {
  <span class="hljs-keyword">if</span> (node) {
    <span class="hljs-keyword">this</span>._mid(node.left)
    <span class="hljs-built_in">console</span>.log(node.value)
    <span class="hljs-keyword">this</span>._mid(node.right)
  }
}
<span class="hljs-comment">// 后序遍历可用于先操作子节点</span>
<span class="hljs-comment">// 再操作父节点的场景</span>
<span class="hljs-comment">// 后序遍历表示先访问左节点，然后访问右节点，最后访问根节点。</span>
backTraversal() {
  <span class="hljs-keyword">this</span>._back(<span class="hljs-keyword">this</span>.root)
}
_back(node) {
  <span class="hljs-keyword">if</span> (node) {
    <span class="hljs-keyword">this</span>._back(node.left)
    <span class="hljs-keyword">this</span>._back(node.right)
    <span class="hljs-built_in">console</span>.log(node.value)
  }
}
</code></pre><p>以上的这几种遍历都可以称之为深度遍历，对应的还有种遍历叫做广度遍历，也就是一层层地遍历树。对于广度遍历来说，我们需要利用之前讲过的队列结构来完成。</p>
<pre><code class="hljs js" lang="js">breadthTraversal() {
  <span class="hljs-keyword">if</span> (!<span class="hljs-keyword">this</span>.root) <span class="hljs-keyword">return</span> <span class="hljs-literal">null</span>
  <span class="hljs-keyword">let</span> q = <span class="hljs-keyword">new</span> Queue()
  <span class="hljs-comment">// 将根节点入队</span>
  q.enQueue(<span class="hljs-keyword">this</span>.root)
  <span class="hljs-comment">// 循环判断队列是否为空，为空</span>
  <span class="hljs-comment">// 代表树遍历完毕</span>
  <span class="hljs-keyword">while</span> (!q.isEmpty()) {
    <span class="hljs-comment">// 将队首出队，判断是否有左右子树</span>
    <span class="hljs-comment">// 有的话，就先左后右入队</span>
    <span class="hljs-keyword">let</span> n = q.deQueue()
    <span class="hljs-built_in">console</span>.log(n.value)
    <span class="hljs-keyword">if</span> (n.left) q.enQueue(n.left)
    <span class="hljs-keyword">if</span> (n.right) q.enQueue(n.right)
  }
}
</code></pre><p>接下来先介绍如何在树中寻找最小值或最大数。因为二分搜索树的特性，所以最小值一定在根节点的最左边，最大值相反</p>
<pre><code class="hljs js" lang="js">getMin() {
  <span class="hljs-keyword">return</span> <span class="hljs-keyword">this</span>._getMin(<span class="hljs-keyword">this</span>.root).value
}
_getMin(node) {
  <span class="hljs-keyword">if</span> (!node.left) <span class="hljs-keyword">return</span> node
  <span class="hljs-keyword">return</span> <span class="hljs-keyword">this</span>._getMin(node.left)
}
getMax() {
  <span class="hljs-keyword">return</span> <span class="hljs-keyword">this</span>._getMax(<span class="hljs-keyword">this</span>.root).value
}
_getMax(node) {
  <span class="hljs-keyword">if</span> (!node.right) <span class="hljs-keyword">return</span> node
  <span class="hljs-keyword">return</span> <span class="hljs-keyword">this</span>._getMin(node.right)
}
</code></pre><p><strong>向上取整和向下取整</strong>，这两个操作是相反的，所以代码也是类似的，这里只介绍如何向下取整。既然是向下取整，那么根据二分搜索树的特性，值一定在根节点的左侧。只需要一直遍历左子树直到当前节点的值不再大于等于需要的值，然后判断节点是否还拥有右子树。如果有的话，继续上面的递归判断。</p>
<pre><code class="hljs js" lang="js">floor(v) {
  <span class="hljs-keyword">let</span> node = <span class="hljs-keyword">this</span>._floor(<span class="hljs-keyword">this</span>.root, v)
  <span class="hljs-keyword">return</span> node ? node.value : <span class="hljs-literal">null</span>
}
_floor(node, v) {
  <span class="hljs-keyword">if</span> (!node) <span class="hljs-keyword">return</span> <span class="hljs-literal">null</span>
  <span class="hljs-keyword">if</span> (node.value === v) <span class="hljs-keyword">return</span> v
  <span class="hljs-comment">// 如果当前节点值还比需要的值大，就继续递归</span>
  <span class="hljs-keyword">if</span> (node.value &gt; v) {
    <span class="hljs-keyword">return</span> <span class="hljs-keyword">this</span>._floor(node.left, v)
  }
  <span class="hljs-comment">// 判断当前节点是否拥有右子树</span>
  <span class="hljs-keyword">let</span> right = <span class="hljs-keyword">this</span>._floor(node.right, v)
  <span class="hljs-keyword">if</span> (right) <span class="hljs-keyword">return</span> right
  <span class="hljs-keyword">return</span> node
}
</code></pre><p><strong>排名</strong>，这是用于获取给定值的排名或者排名第几的节点的值，这两个操作也是相反的，所以这个只介绍如何获取排名第几的节点的值。对于这个操作而言，我们需要略微的改造点代码，让每个节点拥有一个 <code>size</code> 属性。该属性表示该节点下有多少子节点（包含自身）。</p>
<pre><code class="hljs js" lang="js"><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Node</span> </span>{
  <span class="hljs-keyword">constructor</span>(value) {
    <span class="hljs-keyword">this</span>.value = value
    <span class="hljs-keyword">this</span>.left = <span class="hljs-literal">null</span>
    <span class="hljs-keyword">this</span>.right = <span class="hljs-literal">null</span>
    <span class="hljs-comment">// 修改代码</span>
    <span class="hljs-keyword">this</span>.size = <span class="hljs-number">1</span>
  }
}
<span class="hljs-comment">// 新增代码</span>
_getSize(node) {
  <span class="hljs-keyword">return</span> node ? node.size : <span class="hljs-number">0</span>
}
_addChild(node, v) {
  <span class="hljs-keyword">if</span> (!node) {
    <span class="hljs-keyword">return</span> <span class="hljs-keyword">new</span> Node(v)
  }
  <span class="hljs-keyword">if</span> (node.value &gt; v) {
    <span class="hljs-comment">// 修改代码</span>
    node.size++
    node.left = <span class="hljs-keyword">this</span>._addChild(node.left, v)
  } <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (node.value &lt; v) {
    <span class="hljs-comment">// 修改代码</span>
    node.size++
    node.right = <span class="hljs-keyword">this</span>._addChild(node.right, v)
  }
  <span class="hljs-keyword">return</span> node
}
select(k) {
  <span class="hljs-keyword">let</span> node = <span class="hljs-keyword">this</span>._select(<span class="hljs-keyword">this</span>.root, k)
  <span class="hljs-keyword">return</span> node ? node.value : <span class="hljs-literal">null</span>
}
_select(node, k) {
  <span class="hljs-keyword">if</span> (!node) <span class="hljs-keyword">return</span> <span class="hljs-literal">null</span>
  <span class="hljs-comment">// 先获取左子树下有几个节点</span>
  <span class="hljs-keyword">let</span> size = node.left ? node.left.size : <span class="hljs-number">0</span>
  <span class="hljs-comment">// 判断 size 是否大于 k</span>
  <span class="hljs-comment">// 如果大于 k，代表所需要的节点在左节点</span>
  <span class="hljs-keyword">if</span> (size &gt; k) <span class="hljs-keyword">return</span> <span class="hljs-keyword">this</span>._select(node.left, k)
  <span class="hljs-comment">// 如果小于 k，代表所需要的节点在右节点</span>
  <span class="hljs-comment">// 注意这里需要重新计算 k，减去根节点除了右子树的节点数量</span>
  <span class="hljs-keyword">if</span> (size &lt; k) <span class="hljs-keyword">return</span> <span class="hljs-keyword">this</span>._select(node.right, k - size - <span class="hljs-number">1</span>)
  <span class="hljs-keyword">return</span> node
}
</code></pre><p>接下来讲解的是二分搜索树中最难实现的部分：删除节点。因为对于删除节点来说，会存在以下几种情况</p>
<ul>
<li>需要删除的节点没有子树</li>
<li>需要删除的节点只有一条子树</li>
<li>需要删除的节点有左右两条树</li>
</ul>
<p>对于前两种情况很好解决，但是第三种情况就有难度了，所以先来实现相对简单的操作：删除最小节点，对于删除最小节点来说，是不存在第三种情况的，删除最大节点操作是和删除最小节点相反的，所以这里也就不再赘述。</p>
<pre><code class="hljs js" lang="js">delectMin() {
  <span class="hljs-keyword">this</span>.root = <span class="hljs-keyword">this</span>._delectMin(<span class="hljs-keyword">this</span>.root)
  <span class="hljs-built_in">console</span>.log(<span class="hljs-keyword">this</span>.root)
}
_delectMin(node) {
  <span class="hljs-comment">// 一直递归左子树</span>
  <span class="hljs-comment">// 如果左子树为空，就判断节点是否拥有右子树</span>
  <span class="hljs-comment">// 有右子树的话就把需要删除的节点替换为右子树</span>
  <span class="hljs-keyword">if</span> ((node != <span class="hljs-literal">null</span>) &amp; !node.left) <span class="hljs-keyword">return</span> node.right
  node.left = <span class="hljs-keyword">this</span>._delectMin(node.left)
  <span class="hljs-comment">// 最后需要重新维护下节点的 `size`</span>
  node.size = <span class="hljs-keyword">this</span>._getSize(node.left) + <span class="hljs-keyword">this</span>._getSize(node.right) + <span class="hljs-number">1</span>
  <span class="hljs-keyword">return</span> node
}
</code></pre><p>最后讲解的就是如何删除任意节点了。对于这个操作，T.Hibbard 在 1962 年提出了解决这个难题的办法，也就是如何解决第三种情况。</p>
<p>当遇到这种情况时，需要取出当前节点的后继节点（也就是当前节点右子树的最小节点）来替换需要删除的节点。然后将需要删除节点的左子树赋值给后继结点，右子树删除后继结点后赋值给他。</p>
<p>你如果对于这个解决办法有疑问的话，可以这样考虑。因为二分搜索树的特性，父节点一定比所有左子节点大，比所有右子节点小。那么当需要删除父节点时，势必需要拿出一个比父节点大的节点来替换父节点。这个节点肯定不存在于左子树，必然存在于右子树。然后又需要保持父节点都是比右子节点小的，那么就可以取出右子树中最小的那个节点来替换父节点。</p>
<pre><code class="hljs js" lang="js">delect(v) {
  <span class="hljs-keyword">this</span>.root = <span class="hljs-keyword">this</span>._delect(<span class="hljs-keyword">this</span>.root, v)
}
_delect(node, v) {
  <span class="hljs-keyword">if</span> (!node) <span class="hljs-keyword">return</span> <span class="hljs-literal">null</span>
  <span class="hljs-comment">// 寻找的节点比当前节点小，去左子树找</span>
  <span class="hljs-keyword">if</span> (node.value &lt; v) {
    node.right = <span class="hljs-keyword">this</span>._delect(node.right, v)
  } <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (node.value &gt; v) {
    <span class="hljs-comment">// 寻找的节点比当前节点大，去右子树找</span>
    node.left = <span class="hljs-keyword">this</span>._delect(node.left, v)
  } <span class="hljs-keyword">else</span> {
    <span class="hljs-comment">// 进入这个条件说明已经找到节点</span>
    <span class="hljs-comment">// 先判断节点是否拥有拥有左右子树中的一个</span>
    <span class="hljs-comment">// 是的话，将子树返回出去，这里和 `_delectMin` 的操作一样</span>
    <span class="hljs-keyword">if</span> (!node.left) <span class="hljs-keyword">return</span> node.right
    <span class="hljs-keyword">if</span> (!node.right) <span class="hljs-keyword">return</span> node.left
    <span class="hljs-comment">// 进入这里，代表节点拥有左右子树</span>
    <span class="hljs-comment">// 先取出当前节点的后继结点，也就是取当前节点右子树的最小值</span>
    <span class="hljs-keyword">let</span> min = <span class="hljs-keyword">this</span>._getMin(node.right)
    <span class="hljs-comment">// 取出最小值后，删除最小值</span>
    <span class="hljs-comment">// 然后把删除节点后的子树赋值给最小值节点</span>
    min.right = <span class="hljs-keyword">this</span>._delectMin(node.right)
    <span class="hljs-comment">// 左子树不动</span>
    min.left = node.left
    node = min
  }
  <span class="hljs-comment">// 维护 size</span>
  node.size = <span class="hljs-keyword">this</span>._getSize(node.left) + <span class="hljs-keyword">this</span>._getSize(node.right) + <span class="hljs-number">1</span>
  <span class="hljs-keyword">return</span> node
}
</code></pre><h2 class="heading" data-id="heading-18">AVL 树</h2>
<h3 class="heading" data-id="heading-19">概念</h3>
<p>二分搜索树实际在业务中是受到限制的，因为并不是严格的 O(logN)，在极端情况下会退化成链表，比如加入一组升序的数字就会造成这种情况。</p>
<p>AVL 树改进了二分搜索树，在 AVL 树中任意节点的左右子树的高度差都不大于 1，这样保证了时间复杂度是严格的 O(logN)。基于此，对 AVL 树增加或删除节点时可能需要旋转树来达到高度的平衡。</p>
<h3 class="heading" data-id="heading-20">实现</h3>
<p>因为 AVL 树是改进了二分搜索树，所以部分代码是于二分搜索树重复的，对于重复内容不作再次解析。</p>
<p>对于 AVL 树来说，添加节点会有四种情况</p>
<p></p><figure><img class="lazyload inited loaded" data-src="https://user-gold-cdn.xitu.io/2018/6/23/1642cc145a0cfb26?imageView2/0/w/1280/h/960/format/webp/ignore-error/1" data-width="800" data-height="566" src="./31-常见数据结构_files/1642cc145a0cfb26"><figcaption></figcaption></figure><p></p>
<p>对于左左情况来说，新增加的节点位于节点 2 的左侧，这时树已经不平衡，需要旋转。因为搜索树的特性，节点比左节点大，比右节点小，所以旋转以后也要实现这个特性。</p>
<p>旋转之前：new &lt; 2 &lt; C &lt; 3 &lt; B &lt; 5 &lt; A，右旋之后节点 3 为根节点，这时候需要将节点 3 的右节点加到节点 5 的左边，最后还需要更新节点的高度。</p>
<p>对于右右情况来说，相反于左左情况，所以不再赘述。</p>
<p>对于左右情况来说，新增加的节点位于节点 4 的右侧。对于这种情况，需要通过两次旋转来达到目的。</p>
<p>首先对节点的左节点左旋，这时树满足左左的情况，再对节点进行一次右旋就可以达到目的。</p>
<pre><code class="hljs js" lang="js"><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Node</span> </span>{
  <span class="hljs-keyword">constructor</span>(value) {
    <span class="hljs-keyword">this</span>.value = value
    <span class="hljs-keyword">this</span>.left = <span class="hljs-literal">null</span>
    <span class="hljs-keyword">this</span>.right = <span class="hljs-literal">null</span>
    <span class="hljs-keyword">this</span>.height = <span class="hljs-number">1</span>
  }
}

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">AVL</span> </span>{
  <span class="hljs-keyword">constructor</span>() {
    <span class="hljs-keyword">this</span>.root = <span class="hljs-literal">null</span>
  }
  addNode(v) {
    <span class="hljs-keyword">this</span>.root = <span class="hljs-keyword">this</span>._addChild(<span class="hljs-keyword">this</span>.root, v)
  }
  _addChild(node, v) {
    <span class="hljs-keyword">if</span> (!node) {
      <span class="hljs-keyword">return</span> <span class="hljs-keyword">new</span> Node(v)
    }
    <span class="hljs-keyword">if</span> (node.value &gt; v) {
      node.left = <span class="hljs-keyword">this</span>._addChild(node.left, v)
    } <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (node.value &lt; v) {
      node.right = <span class="hljs-keyword">this</span>._addChild(node.right, v)
    } <span class="hljs-keyword">else</span> {
      node.value = v
    }
    node.height =
      <span class="hljs-number">1</span> + <span class="hljs-built_in">Math</span>.max(<span class="hljs-keyword">this</span>._getHeight(node.left), <span class="hljs-keyword">this</span>._getHeight(node.right))
    <span class="hljs-keyword">let</span> factor = <span class="hljs-keyword">this</span>._getBalanceFactor(node)
    <span class="hljs-comment">// 当需要右旋时，根节点的左树一定比右树高度高</span>
    <span class="hljs-keyword">if</span> (factor &gt; <span class="hljs-number">1</span> &amp;&amp; <span class="hljs-keyword">this</span>._getBalanceFactor(node.left) &gt;= <span class="hljs-number">0</span>) {
      <span class="hljs-keyword">return</span> <span class="hljs-keyword">this</span>._rightRotate(node)
    }
    <span class="hljs-comment">// 当需要左旋时，根节点的左树一定比右树高度矮</span>
    <span class="hljs-keyword">if</span> (factor &lt; <span class="hljs-number">-1</span> &amp;&amp; <span class="hljs-keyword">this</span>._getBalanceFactor(node.right) &lt;= <span class="hljs-number">0</span>) {
      <span class="hljs-keyword">return</span> <span class="hljs-keyword">this</span>._leftRotate(node)
    }
    <span class="hljs-comment">// 左右情况</span>
    <span class="hljs-comment">// 节点的左树比右树高，且节点的左树的右树比节点的左树的左树高</span>
    <span class="hljs-keyword">if</span> (factor &gt; <span class="hljs-number">1</span> &amp;&amp; <span class="hljs-keyword">this</span>._getBalanceFactor(node.left) &lt; <span class="hljs-number">0</span>) {
      node.left = <span class="hljs-keyword">this</span>._leftRotate(node.left)
      <span class="hljs-keyword">return</span> <span class="hljs-keyword">this</span>._rightRotate(node)
    }
    <span class="hljs-comment">// 右左情况</span>
    <span class="hljs-comment">// 节点的左树比右树矮，且节点的右树的右树比节点的右树的左树矮</span>
    <span class="hljs-keyword">if</span> (factor &lt; <span class="hljs-number">-1</span> &amp;&amp; <span class="hljs-keyword">this</span>._getBalanceFactor(node.right) &gt; <span class="hljs-number">0</span>) {
      node.right = <span class="hljs-keyword">this</span>._rightRotate(node.right)
      <span class="hljs-keyword">return</span> <span class="hljs-keyword">this</span>._leftRotate(node)
    }

    <span class="hljs-keyword">return</span> node
  }
  _getHeight(node) {
    <span class="hljs-keyword">if</span> (!node) <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>
    <span class="hljs-keyword">return</span> node.height
  }
  _getBalanceFactor(node) {
    <span class="hljs-keyword">return</span> <span class="hljs-keyword">this</span>._getHeight(node.left) - <span class="hljs-keyword">this</span>._getHeight(node.right)
  }
  <span class="hljs-comment">// 节点右旋</span>
  <span class="hljs-comment">//           5                    2</span>
  <span class="hljs-comment">//         /   \                /   \</span>
  <span class="hljs-comment">//        2     6   ==&gt;       1      5</span>
  <span class="hljs-comment">//       /  \               /       /  \</span>
  <span class="hljs-comment">//      1    3             new     3    6</span>
  <span class="hljs-comment">//     /</span>
  <span class="hljs-comment">//    new</span>
  _rightRotate(node) {
    <span class="hljs-comment">// 旋转后新根节点</span>
    <span class="hljs-keyword">let</span> newRoot = node.left
    <span class="hljs-comment">// 需要移动的节点</span>
    <span class="hljs-keyword">let</span> moveNode = newRoot.right
    <span class="hljs-comment">// 节点 2 的右节点改为节点 5</span>
    newRoot.right = node
    <span class="hljs-comment">// 节点 5 左节点改为节点 3</span>
    node.left = moveNode
    <span class="hljs-comment">// 更新树的高度</span>
    node.height =
      <span class="hljs-number">1</span> + <span class="hljs-built_in">Math</span>.max(<span class="hljs-keyword">this</span>._getHeight(node.left), <span class="hljs-keyword">this</span>._getHeight(node.right))
    newRoot.height =
      <span class="hljs-number">1</span> +
      <span class="hljs-built_in">Math</span>.max(<span class="hljs-keyword">this</span>._getHeight(newRoot.left), <span class="hljs-keyword">this</span>._getHeight(newRoot.right))

    <span class="hljs-keyword">return</span> newRoot
  }
  <span class="hljs-comment">// 节点左旋</span>
  <span class="hljs-comment">//           4                    6</span>
  <span class="hljs-comment">//         /   \                /   \</span>
  <span class="hljs-comment">//        2     6   ==&gt;       4      7</span>
  <span class="hljs-comment">//             /  \         /   \      \</span>
  <span class="hljs-comment">//            5     7      2     5      new</span>
  <span class="hljs-comment">//                   \</span>
  <span class="hljs-comment">//                    new</span>
  _leftRotate(node) {
    <span class="hljs-comment">// 旋转后新根节点</span>
    <span class="hljs-keyword">let</span> newRoot = node.right
    <span class="hljs-comment">// 需要移动的节点</span>
    <span class="hljs-keyword">let</span> moveNode = newRoot.left
    <span class="hljs-comment">// 节点 6 的左节点改为节点 4</span>
    newRoot.left = node
    <span class="hljs-comment">// 节点 4 右节点改为节点 5</span>
    node.right = moveNode
    <span class="hljs-comment">// 更新树的高度</span>
    node.height =
      <span class="hljs-number">1</span> + <span class="hljs-built_in">Math</span>.max(<span class="hljs-keyword">this</span>._getHeight(node.left), <span class="hljs-keyword">this</span>._getHeight(node.right))
    newRoot.height =
      <span class="hljs-number">1</span> +
      <span class="hljs-built_in">Math</span>.max(<span class="hljs-keyword">this</span>._getHeight(newRoot.left), <span class="hljs-keyword">this</span>._getHeight(newRoot.right))

    <span class="hljs-keyword">return</span> newRoot
  }
}
</code></pre><h2 class="heading" data-id="heading-21">Trie</h2>
<h3 class="heading" data-id="heading-22">概念</h3>
<p>在计算机科学，<strong>trie</strong>，又称<strong>前缀树</strong>或<strong>字典树</strong>，是一种有序树，用于保存关联数组，其中的键通常是字符串。</p>
<p>简单点来说，这个结构的作用大多是为了方便搜索字符串，该树有以下几个特点</p>
<ul>
<li>根节点代表空字符串，每个节点都有 N（假如搜索英文字符，就有 26 条） 条链接，每条链接代表一个字符</li>
<li>节点不存储字符，只有路径才存储，这点和其他的树结构不同</li>
<li>从根节点开始到任意一个节点，将沿途经过的字符连接起来就是该节点对应的字符串</li>
</ul>
<p></p><figure><img class="lazyload inited loaded" data-src="https://user-gold-cdn.xitu.io/2018/6/9/163e1d2f6cec3348?imageView2/0/w/1280/h/960/format/webp/ignore-error/1" data-width="640" data-height="600" src="./31-常见数据结构_files/163e1d2f6cec3348"><figcaption></figcaption></figure>、<p></p>
<h3 class="heading" data-id="heading-23">实现</h3>
<p>总得来说 Trie 的实现相比别的树结构来说简单的很多，实现就以搜索英文字符为例。</p>
<pre><code class="hljs js" lang="js"><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">TrieNode</span> </span>{
  <span class="hljs-keyword">constructor</span>() {
    <span class="hljs-comment">// 代表每个字符经过节点的次数</span>
    <span class="hljs-keyword">this</span>.path = <span class="hljs-number">0</span>
    <span class="hljs-comment">// 代表到该节点的字符串有几个</span>
    <span class="hljs-keyword">this</span>.end = <span class="hljs-number">0</span>
    <span class="hljs-comment">// 链接</span>
    <span class="hljs-keyword">this</span>.next = <span class="hljs-keyword">new</span> <span class="hljs-built_in">Array</span>(<span class="hljs-number">26</span>).fill(<span class="hljs-literal">null</span>)
  }
}
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Trie</span> </span>{
  <span class="hljs-keyword">constructor</span>() {
    <span class="hljs-comment">// 根节点，代表空字符</span>
    <span class="hljs-keyword">this</span>.root = <span class="hljs-keyword">new</span> TrieNode()
  }
  <span class="hljs-comment">// 插入字符串</span>
  insert(str) {
    <span class="hljs-keyword">if</span> (!str) <span class="hljs-keyword">return</span>
    <span class="hljs-keyword">let</span> node = <span class="hljs-keyword">this</span>.root
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-number">0</span>; i &lt; str.length; i++) {
      <span class="hljs-comment">// 获得字符先对应的索引</span>
      <span class="hljs-keyword">let</span> index = str[i].charCodeAt() - <span class="hljs-string">'a'</span>.charCodeAt()
      <span class="hljs-comment">// 如果索引对应没有值，就创建</span>
      <span class="hljs-keyword">if</span> (!node.next[index]) {
        node.next[index] = <span class="hljs-keyword">new</span> TrieNode()
      }
      node.path += <span class="hljs-number">1</span>
      node = node.next[index]
    }
    node.end += <span class="hljs-number">1</span>
  }
  <span class="hljs-comment">// 搜索字符串出现的次数</span>
  search(str) {
    <span class="hljs-keyword">if</span> (!str) <span class="hljs-keyword">return</span>
    <span class="hljs-keyword">let</span> node = <span class="hljs-keyword">this</span>.root
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-number">0</span>; i &lt; str.length; i++) {
      <span class="hljs-keyword">let</span> index = str[i].charCodeAt() - <span class="hljs-string">'a'</span>.charCodeAt()
      <span class="hljs-comment">// 如果索引对应没有值，代表没有需要搜素的字符串</span>
      <span class="hljs-keyword">if</span> (!node.next[index]) {
        <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>
      }
      node = node.next[index]
    }
    <span class="hljs-keyword">return</span> node.end
  }
  <span class="hljs-comment">// 删除字符串</span>
  <span class="hljs-keyword">delete</span>(str) {
    <span class="hljs-keyword">if</span> (!<span class="hljs-keyword">this</span>.search(str)) <span class="hljs-keyword">return</span>
    <span class="hljs-keyword">let</span> node = <span class="hljs-keyword">this</span>.root
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-number">0</span>; i &lt; str.length; i++) {
      <span class="hljs-keyword">let</span> index = str[i].charCodeAt() - <span class="hljs-string">'a'</span>.charCodeAt()
      <span class="hljs-comment">// 如果索引对应的节点的 Path 为 0，代表经过该节点的字符串</span>
      <span class="hljs-comment">// 已经一个，直接删除即可</span>
      <span class="hljs-keyword">if</span> (--node.next[index].path == <span class="hljs-number">0</span>) {
        node.next[index] = <span class="hljs-literal">null</span>
        <span class="hljs-keyword">return</span>
      }
      node = node.next[index]
    }
    node.end -= <span class="hljs-number">1</span>
  }
}
</code></pre><h2 class="heading" data-id="heading-24">并查集</h2>
<h3 class="heading" data-id="heading-25">概念</h3>
<p>并查集是一种特殊的树结构，用于处理一些不交集的合并及查询问题。该结构中每个节点都有一个父节点，如果只有当前一个节点，那么该节点的父节点指向自己。</p>
<p>这个结构中有两个重要的操作，分别是：</p>
<ul>
<li>Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。</li>
<li>Union：将两个子集合并成同一个集合。</li>
</ul>
<p></p><figure><img class="lazyload inited loaded" data-src="https://user-gold-cdn.xitu.io/2018/6/9/163e45b56fd25172?imageView2/0/w/1280/h/960/format/webp/ignore-error/1" data-width="421" data-height="209" src="./31-常见数据结构_files/163e45b56fd25172"><figcaption></figcaption></figure><p></p>
<h3 class="heading" data-id="heading-26">实现</h3>
<pre><code class="hljs js" lang="js"><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">DisjointSet</span> </span>{
  <span class="hljs-comment">// 初始化样本</span>
  <span class="hljs-keyword">constructor</span>(count) {
    <span class="hljs-comment">// 初始化时，每个节点的父节点都是自己</span>
    <span class="hljs-keyword">this</span>.parent = <span class="hljs-keyword">new</span> <span class="hljs-built_in">Array</span>(count)
    <span class="hljs-comment">// 用于记录树的深度，优化搜索复杂度</span>
    <span class="hljs-keyword">this</span>.rank = <span class="hljs-keyword">new</span> <span class="hljs-built_in">Array</span>(count)
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-number">0</span>; i &lt; count; i++) {
      <span class="hljs-keyword">this</span>.parent[i] = i
      <span class="hljs-keyword">this</span>.rank[i] = <span class="hljs-number">1</span>
    }
  }
  find(p) {
    <span class="hljs-comment">// 寻找当前节点的父节点是否为自己，不是的话表示还没找到</span>
    <span class="hljs-comment">// 开始进行路径压缩优化</span>
    <span class="hljs-comment">// 假设当前节点父节点为 A</span>
    <span class="hljs-comment">// 将当前节点挂载到 A 节点的父节点上，达到压缩深度的目的</span>
    <span class="hljs-keyword">while</span> (p != <span class="hljs-keyword">this</span>.parent[p]) {
      <span class="hljs-keyword">this</span>.parent[p] = <span class="hljs-keyword">this</span>.parent[<span class="hljs-keyword">this</span>.parent[p]]
      p = <span class="hljs-keyword">this</span>.parent[p]
    }
    <span class="hljs-keyword">return</span> p
  }
  isConnected(p, q) {
    <span class="hljs-keyword">return</span> <span class="hljs-keyword">this</span>.find(p) === <span class="hljs-keyword">this</span>.find(q)
  }
  <span class="hljs-comment">// 合并</span>
  union(p, q) {
    <span class="hljs-comment">// 找到两个数字的父节点</span>
    <span class="hljs-keyword">let</span> i = <span class="hljs-keyword">this</span>.find(p)
    <span class="hljs-keyword">let</span> j = <span class="hljs-keyword">this</span>.find(q)
    <span class="hljs-keyword">if</span> (i === j) <span class="hljs-keyword">return</span>
    <span class="hljs-comment">// 判断两棵树的深度，深度小的加到深度大的树下面</span>
    <span class="hljs-comment">// 如果两棵树深度相等，那就无所谓怎么加</span>
    <span class="hljs-keyword">if</span> (<span class="hljs-keyword">this</span>.rank[i] &lt; <span class="hljs-keyword">this</span>.rank[j]) {
      <span class="hljs-keyword">this</span>.parent[i] = j
    } <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (<span class="hljs-keyword">this</span>.rank[i] &gt; <span class="hljs-keyword">this</span>.rank[j]) {
      <span class="hljs-keyword">this</span>.parent[j] = i
    } <span class="hljs-keyword">else</span> {
      <span class="hljs-keyword">this</span>.parent[i] = j
      <span class="hljs-keyword">this</span>.rank[j] += <span class="hljs-number">1</span>
    }
  }
}
</code></pre><h2 class="heading" data-id="heading-27">堆</h2>
<h3 class="heading" data-id="heading-28">概念</h3>
<p>堆通常是一个可以被看做一棵树的数组对象。</p>
<p>堆的实现通过构造<strong>二叉堆</strong>，实为二叉树的一种。这种数据结构具有以下性质。</p>
<ul>
<li>任意节点小于（或大于）它的所有子节点</li>
<li>堆总是一棵完全树。即除了最底层，其他层的节点都被元素填满，且最底层从左到右填入。</li>
</ul>
<p>将根节点最大的堆叫做<strong>最大堆</strong>或<strong>大根堆</strong>，根节点最小的堆叫做<strong>最小堆</strong>或<strong>小根堆</strong>。</p>
<p>优先队列也完全可以用堆来实现，操作是一模一样的。</p>
<h3 class="heading" data-id="heading-29">实现大根堆</h3>
<p>堆的每个节点的左边子节点索引是 <code>i * 2 + 1</code>，右边是 <code>i * 2 + 2</code>，父节点是 <code>(i - 1) /2</code>。</p>
<p>堆有两个核心的操作，分别是 <code>shiftUp</code> 和 <code>shiftDown</code> 。前者用于添加元素，后者用于删除根节点。</p>
<p><code>shiftUp</code> 的核心思路是一路将节点与父节点对比大小，如果比父节点大，就和父节点交换位置。</p>
<p><code>shiftDown</code> 的核心思路是先将根节点和末尾交换位置，然后移除末尾元素。接下来循环判断父节点和两个子节点的大小，如果子节点大，就把最大的子节点和父节点交换。</p>
<p></p><figure><img class="lazyload inited loaded" data-src="https://user-gold-cdn.xitu.io/2018/6/15/164009e58a5a21f8?imageView2/0/w/1280/h/960/format/webp/ignore-error/1" data-width="537" data-height="394" src="./31-常见数据结构_files/164009e58a5a21f8"><figcaption></figcaption></figure><p></p>
<pre><code class="hljs js" lang="js"><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">MaxHeap</span> </span>{
  <span class="hljs-keyword">constructor</span>() {
    <span class="hljs-keyword">this</span>.heap = []
  }
  size() {
    <span class="hljs-keyword">return</span> <span class="hljs-keyword">this</span>.heap.length
  }
  empty() {
    <span class="hljs-keyword">return</span> <span class="hljs-keyword">this</span>.size() == <span class="hljs-number">0</span>
  }
  add(item) {
    <span class="hljs-keyword">this</span>.heap.push(item)
    <span class="hljs-keyword">this</span>._shiftUp(<span class="hljs-keyword">this</span>.size() - <span class="hljs-number">1</span>)
  }
  removeMax() {
    <span class="hljs-keyword">this</span>._shiftDown(<span class="hljs-number">0</span>)
  }
  getParentIndex(k) {
    <span class="hljs-keyword">return</span> <span class="hljs-built_in">parseInt</span>((k - <span class="hljs-number">1</span>) / <span class="hljs-number">2</span>)
  }
  getLeftIndex(k) {
    <span class="hljs-keyword">return</span> k * <span class="hljs-number">2</span> + <span class="hljs-number">1</span>
  }
  _shiftUp(k) {
    <span class="hljs-comment">// 如果当前节点比父节点大，就交换</span>
    <span class="hljs-keyword">while</span> (<span class="hljs-keyword">this</span>.heap[k] &gt; <span class="hljs-keyword">this</span>.heap[<span class="hljs-keyword">this</span>.getParentIndex(k)]) {
      <span class="hljs-keyword">this</span>._swap(k, <span class="hljs-keyword">this</span>.getParentIndex(k))
      <span class="hljs-comment">// 将索引变成父节点</span>
      k = <span class="hljs-keyword">this</span>.getParentIndex(k)
    }
  }
  _shiftDown(k) {
    <span class="hljs-comment">// 交换首位并删除末尾</span>
    <span class="hljs-keyword">this</span>._swap(k, <span class="hljs-keyword">this</span>.size() - <span class="hljs-number">1</span>)
    <span class="hljs-keyword">this</span>.heap.splice(<span class="hljs-keyword">this</span>.size() - <span class="hljs-number">1</span>, <span class="hljs-number">1</span>)
    <span class="hljs-comment">// 判断节点是否有左孩子，因为二叉堆的特性，有右必有左</span>
    <span class="hljs-keyword">while</span> (<span class="hljs-keyword">this</span>.getLeftIndex(k) &lt; <span class="hljs-keyword">this</span>.size()) {
      <span class="hljs-keyword">let</span> j = <span class="hljs-keyword">this</span>.getLeftIndex(k)
      <span class="hljs-comment">// 判断是否有右孩子，并且右孩子是否大于左孩子</span>
      <span class="hljs-keyword">if</span> (j + <span class="hljs-number">1</span> &lt; <span class="hljs-keyword">this</span>.size() &amp;&amp; <span class="hljs-keyword">this</span>.heap[j + <span class="hljs-number">1</span>] &gt; <span class="hljs-keyword">this</span>.heap[j]) j++
      <span class="hljs-comment">// 判断父节点是否已经比子节点都大</span>
      <span class="hljs-keyword">if</span> (<span class="hljs-keyword">this</span>.heap[k] &gt;= <span class="hljs-keyword">this</span>.heap[j]) <span class="hljs-keyword">break</span>
      <span class="hljs-keyword">this</span>._swap(k, j)
      k = j
    }
  }
  _swap(left, right) {
    <span class="hljs-keyword">let</span> rightValue = <span class="hljs-keyword">this</span>.heap[right]
    <span class="hljs-keyword">this</span>.heap[right] = <span class="hljs-keyword">this</span>.heap[left]
    <span class="hljs-keyword">this</span>.heap[left] = rightValue
  }
}
</code></pre><h2 class="heading" data-id="heading-30">小结</h2>
<p>这一章节我们学习了一些常见的数据结构，当然我没有将其他更难的数据结构也放进来，能够掌握这些常见的内容已经足够解决大部分的问题了。当然你如果还想继续深入学习数据结构，可以阅读 <a target="_blank" href="https://link.juejin.im/?target=https%3A%2F%2Fbook.douban.com%2Fsubject%2F19952400%2F" rel="nofollow noopener noreferrer">算法第四版</a> 以及在 <a target="_blank" href="https://link.juejin.im/?target=https%3A%2F%2Fleetcode-cn.com%2Fproblemset%2Fall%2F" rel="nofollow noopener noreferrer">leetcode</a> 中实践。</p>
</div><section data-v-05bbf43a="" class="book-comments"><div data-v-05bbf43a="" class="box-title">留言</div><div data-v-05bbf43a="" class="comment-box"><div data-v-81313b1e="" data-v-05bbf43a="" class="comment-form comment-form" id="comment"><div data-v-3b1ba6d2="" data-v-afcc6e34="" data-v-81313b1e="" data-src="https://b-gold-cdn.xitu.io/v3/static/img/default-avatar.e30559a.svg" class="lazy avatar avatar loaded" style="background-image: url(&quot;https://b-gold-cdn.xitu.io/v3/static/img/default-avatar.e30559a.svg&quot;);"></div><textarea data-v-81313b1e="" placeholder="评论将在后台进行审核，审核通过后对所有人可见" class="content-input" style="overflow: hidden; overflow-wrap: break-word; height: 60px;"></textarea><div data-v-81313b1e="" class="action-box" style="display: none;"><div data-v-680eb36d="" data-v-81313b1e="" class="image-uploader image-uploader" style="display: none;"><input data-v-680eb36d="" type="file" class="input"><button data-v-680eb36d="" class="upload-btn"><i data-v-680eb36d="" class="icon ion-image"></i><span data-v-680eb36d="">上传图片</span></button></div><div data-v-81313b1e="" class="submit-box"><span data-v-81313b1e="" class="submit-text">Ctrl or ⌘ + Enter</span><button data-v-81313b1e="" class="submit-btn">评论</button></div></div><!----></div></div><ul data-v-32e5a55b="" data-v-05bbf43a="" st:block="commentList" class="comment-list comment-list"><!----></ul></section></div></div><!----><!----></div></div><div data-v-a9263a68="" data-v-097468bb="" class="book-handle book-direction"><div data-v-a9263a68="" class="step-btn step-btn--prev"><img data-v-a9263a68="" src="./31-常见数据结构_files/prev.87ad47e.svg"></div><div data-v-a9263a68="" class="step-btn step-btn--next"><img data-v-a9263a68="" src="./31-常见数据结构_files/next.54d8a35.svg"></div><!----><!----></div><!----></div></div></section><!----><!----><!----><div data-v-1b0b9cb8="" data-v-097468bb="" class="image-viewer-box"><!----></div></div><!----></div>
      
      
      <script type="text/javascript" src="./31-常见数据结构_files/runtime.5902a8b1cc2b7567f479.js.下载"></script><script type="text/javascript" src="./31-常见数据结构_files/0.e205fcdd4d4b6767f462.js.下载"></script><script type="text/javascript" src="./31-常见数据结构_files/1.cbb1f8f5dcdee0086c6a.js.下载"></script>
    </body></html>